package com.sicheng.datastruct.tree;

import com.sicheng.datastruct.tree.utils.TreeUtil;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/27 16:13
 */
public class GetNext {


    public static HeroNode getNextForInorder(HeroNode target) {
        if (target == null)
            return null;

        if (target.right != null) {
            target = target.right;
            while (target.left != null)
                target = target.left;
            return target;
        } else {
            while (target.parent != null) {
                if (target.parent.left == target)
                    return target.parent;
                target = target.parent;
            }
        }
        return null;
    }

    public static void initTreesParent(HeroNode root, HeroNode parent) {
        if (root.left != null) {
            HeroNode left = root.left;
            left.parent = root;
            initTreesParent(left, root);
        }
        root.parent = parent;

        if (root.right != null) {
            HeroNode right = root.right;
            right.parent = root;
            initTreesParent(right, root);
        }


    }


    public static void main(String[] args) {

        ReBuildBinaryTree buildBinaryTreeTool =
                new ReBuildBinaryTree(new Integer[]{3, 9, 20, 15, 7}, new Integer[]{9, 3, 15, 20, 7});

        HeroNode root = buildBinaryTreeTool.rebuild();
        initTreesParent(root, null);

        System.out.println(getNextForInorder(root.right.right));
        int size = TreeUtil.sizeOfTree(root);
        System.out.println(size);
    }

}
